package org.example.leetcode;

import java.util.Arrays;

/**
 * @version 1.0.0
 * @author: lynn
 * @description: 零钱兑换I,获取最少零钱个数
 * @date: 2021/7/25 10:15
 */
public class LC322 {

    public static void main(String[] args) {
        int[] coins=new int[]{1,2,5,10,20,50,100};
        int amount=87;
        LC322 lc=new LC322();
        System.out.println(lc.coinChange(coins,amount));
    }
    //动态规划，找零钱的问题
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);//fixme 你现在想要小，所以都要变大
        dp[0]=0;
        for (int curAmount=1;curAmount<=amount;curAmount++){
            for (int coin:coins){
                int leftAmount=curAmount-coin;
                //fixme 这里不能等于0? 等于0也要参与计算，小于0不用
                if (leftAmount<0 ||dp[leftAmount]==Integer.MAX_VALUE) continue;
                dp[curAmount]=Math.min(dp[leftAmount]+1,dp[curAmount]);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}